#include <iostream>

typedef char char_t;

const static int INF_SCORE = 32767;
const static int cost_copy = 0;
const static int cost_replace = 1;
const static int cost_delete = 1;
const static int cost_insert = 1;
const static int cost_exchange = 1;
const static int cost_kill = 10;

char** op;
int kill_index = 0;
int m, n;

/*
 * compute edit distance from string A to String B.(different form B to A)
 */
int compute_edit_distance( char_t* A, char_t* B )
{
  m = strlen(A) + 1;
  n = strlen(B) + 1;

  // init c[m][n]
  int **c = new int*[m];
  c[0] = new int[m*n];
  for( int i = 1; i < m; i++ ){
    c[i] = c[i-1] + n;
  }

  // init op[m][n]
  op = new char*[m];
  op[0] = new char[m*n];
  for( int i = 1; i < m; i++ )
    op[i] = op[i-1] + n;

  
  for( int i = 0; i < m; i++ ){
	 c[i][0] = i*cost_delete;
	 op[i][0] = 'd';
  }

  for( int i = 0; i < n; i++ ){
	 c[0][i] = i*cost_insert;
	 op[0][i] = 'i';
  }


  for( int i = 1; i < m; i++ )
    for( int j = 1; j < n; j++ ) {
	   c[i][j] = INF_SCORE;
      if( A[i-1] == B[j-1] ){
		  c[i][j] = c[i-1][j-1] + cost_copy;
		  op[i][j] = 'c';
      }
	   if( A[i-1] != B[j-1] && c[i-1][j-1] + cost_replace < c[i][j] ) {
		  c[i][j] = c[i-1][j-1] + cost_replace;
		  op[i][j] = 'r';
      }
	   if( c[i-1][j] + cost_delete < c[i][j] ) {
		  c[i][j] = c[i-1][j] + cost_delete;
		  op[i][j] = 'd';
      }
	   if( c[i][j-1] + cost_insert < c[i][j] ) {
		 c[i][j] = c[i][j-1] + cost_insert;
		 op[i][j] = 'i';
	   }
	   if( i >= 2 && j >=2 && A[i-1] == B[j-2] && A[i-2] == B[j-1] && c[i-2][j-2] + cost_exchange < c[i][j] ) {
		 c[i][j] = c[i-2][j-2] + cost_exchange;
		 op[i][j] = 'e';
		 
	   }
    }

  for( int i = 0; i < m; i++ ){
	if( c[i][n-1] + cost_kill < c[m-1][n-1] ) {
	  c[m-1][n-1] = c[i][n-1] + cost_kill;
	  op[m-1][n-1] = 'k';
	  kill_index = i;
	}
  }
   
  
  int result = c[m-1][n-1];
  
  delete[] c[0];
  delete[] c;

  return result;
}

void print_op_sequence(int i, int j)
{
  int ii, jj;
  if( i <= 0 && j <= 0 )
	return;

  if( op[i][j] == 'c' || op[i][j] == 'r' ){
	ii = i - 1;
	jj = j - 1;
  } else if( op[i][j] == 'd' ){
	ii = i - 1;
	jj = j;
  } else if( op[i][j] == 'i' ){
	jj = j - 1;
	ii = i;
  } else if( op[i][j] == 'e' ){
	ii = i - 2;
	jj = j - 2;
  } else if( op[i][j] == 'k' ){
	ii = kill_index;
	jj = j;
  } else {
	::std::cout << "unvalid operator!" << ::std::endl;
	exit(-1);
  }

  print_op_sequence( ii, jj );
  ::std::cout<< op[i][j] << '\t';

  return;
}

int main()
{
  ::std::cout << compute_edit_distance( "12433", "12343" ) << ::std::endl;
  print_op_sequence( m-1, n-1 );
  return 1;
}
